/* tree1.h -- binary search tree1                          */
/*           no duplicate items are allowed in this tree1 */
#ifndef _TREE_H_
#define _TREE_H_
#include <stdbool.h>

/* redefine Item as appropriate */
#define SLEN 20
//typedef struct item
//{
//    char petname[SLEN];
//    char petkind[SLEN];
//} Item;

#define MAXLEN 81
typedef struct word {
    char string[MAXLEN];
    int size;
} Item;
#define MAXITEMS 100*100

typedef struct trnode
{
    Item item;
    struct trnode * left;  /* pointer to right branch  */
    struct trnode * right; /* pointer to left branch   */
} Trnode;

typedef struct tree1
{
    Trnode * root;         /* pointer to root of tree1  */
    int size;              /* number of items in tree1  */
} Tree;

/* function prototypes */

/* operation:      initialize a tree1 to empty          */
/* preconditions:  ptree points to a tree1              */
/* postconditions: the tree1 is initialized to empty    */
void InitializeTree(Tree * ptree);

/* operation:      determine if tree1 is empty          */
/* preconditions:  ptree points to a tree1              */
/* postconditions: function returns true if tree1 is    */
/*                 empty and returns false otherwise   */
bool TreeIsEmpty(const Tree * ptree);

/* operation:      determine if tree1 is full           */
/* preconditions:  ptree points to a tree1              */
/* postconditions: function returns true if tree1 is    */
/*                 full and returns false otherwise    */
bool TreeIsFull(const Tree * ptree);

/* operation:      determine number of items in tree1   */
/* preconditions:  ptree points to a tree1              */
/* postconditions: function returns number of items in */
/*                 tree1                                */
int TreeItemCount(const Tree * ptree);

/* operation:      add an item to a tree1               */
/* preconditions:  pi is address of item to be added   */
/*                 ptree points to an initialized tree1 */
/* postconditions: if possible, function adds item to  */
/*                 tree1 and returns true; otherwise,   */
/*                 the function returns false          */
bool AddItem(const Item * pi, Tree * ptree);

/* operation: find an item in a tree1                   */
/* preconditions:  pi points to an item                */
/*                 ptree points to an initialized tree1 */
/* postconditions: function returns true if item is in */
/*                 tree1 and returns false otherwise    */
bool InTree(const Item * pi, const Tree * ptree);

/* operation:      delete an item from a tree1          */
/* preconditions:  pi is address of item to be deleted */
/*                 ptree points to an initialized tree1 */
/* postconditions: if possible, function deletes item  */
/*                 from tree1 and returns true;         */
/*                 otherwise the function returns false*/
bool DeleteItem(const Item * pi, Tree * ptree);

/* operation:      apply a function to each item in    */
/*                 the tree1                            */
/* preconditions:  ptree points to a tree1              */
/*                 pfun points to a function that takes*/
/*                 an Item argument and has no return  */
/*                 value                               */
/* postcondition:  the function pointed to by pfun is  */
/*                 executed once for each item in tree1 */
void Traverse (const Tree * ptree, void (* pfun)(Item item));

/* operation:      delete everything from a tree1       */
/* preconditions:  ptree points to an initialized tree1 */
/* postconditions: tree1 is empty                       */
void DeleteAll(Tree * ptree);

Item* findItem(Item *item,Tree * ptree);
#endif
